Subliminal channels
Subliminal channels in digital signature crypto systems were found in 1984 by Gustavus Simmons. They are a subgroup of Covert channels and can be used to communicate secretly in a normal looking communication over an insecure channel with help of digital signatures Gustavus J. Simmons. The Prisoners Problem and the Subliminal Channel. In Advances in Cryptology – CRYPTO ’83, pages 51–67, New York, 1984. Lecture Notes in Computer Science, ed. D. Chaum.. Simmons describes how the dilemma can be solved through parameter substitution in digital signature algorithms Gustavus J. Simmons. The subliminal channel and digital signatures. In Proc. of the EUROCRYPT 84 workshop on Advances in cryptology: theory and application of cryptographic techniques, pages 364–378, New York, NY, USA, 1985. Springer-Verlag New York, Inc.. In signature algorithms like ElGamal and DSA exist parameters which have to be set with random. He shows how one can make usage of these parameter to send a message subliminally. Because the algorithm's signature creation procedure is unchanged, the signature remains verifiable and indistinguishable from a normal signature. Therefore it is hard to detect if the subliminal channel is used. Subliminal channels can be classified into broadband and narrow-band channel. The broadband channel uses almost all available bits. Every channel which uses less bits is called a narrow-band channel. The additionally used bits are needed for further protection, e.g., impersonation. The broadband and the narrow-band channels can use different algorithm parameters. A narrow-band channel cannot transport maximal information, but it preserves the authentication key. Further developments enhance the subliminal channel, e.g., allow for establishing a broadband channel without the need to agree on an authentication key in advance. Other developments try to avoid the entire subliminal channel. Examples The easiest way to establish a subliminal channel is, to define that an even word count in a sentence is associated with the bit "0" and an odd word count with the bit "1". The question "Hello, how do you do?" would therefore send the subliminal message "1". The Digital Signature Algorithm has a subliminal broadbandGustavus J. Simmons. Subliminal communication is easy using the DSA. In EUROCRYPT ’93: Workshop on the theory and application of cryptographic techniques on Advances in cryptology, pages 218–232, Secaucus, NJ, USA, 1994. Springer-Verlag New York, Inc. and three subliminal narrow-band channels Gustavus J. Simmons. The subliminal channel in the U.S. Digital Signature Algorithm (DSA), 1993. At signing the parameter k has to be set random. For the broadband channel this parameter is instead set with a subliminal message m' . # Key generation ## choose prime p = 2347 ## choose prime q = 23 ## calculate generator g = 266 ## choose authentication key x = 1468 and send it securely to the receiver ## calculate public key y = g^x mod p = 2100 # Signing ## choose message m = 1337 ## (hash function H(m) is here substituted with a modulo reduction by 107) calculate message hash value h = m mod q = 1337 mod 107 = 53 ## instead of random value k = ? subliminal message m' = 17 is chosen ## calculate inverse of the subliminal message m'^{-1} = 19 mod 23 ## calculate signature value r = (g^k mod p) mod q = (266^{17} mod 2347) mod 23 = 12 ## calculate signature value s = k^{-1} * (h + x*r) mod q = 19 * (53 + 1468 * 12) mod 23 = 3 ## sending message with signature triple (1337; 12, 3) # Verifying ## receiver gets message triple (m; r, s) = (1337; 12, 3) ## calculate message hash h = H(m) mod q = 1337 mod 107 = 53 ## calculate inverse w = s^{-1} mod q = 8 ## calculate u_1 = (h * w) mod q = 53 * 8 mod 23 = 10 ## calculate u_2 = (r * w) mod q = 12 * 8 mod 23 = 4 ## calculate signature v = (g^{u_1} * y^{u_2} mod p) mod q = (266^{10} * 2100^4 mod 2347) mod 23 = 12 ## since v = r , the is signature valid # Message extraction on receiver side ## from triple (1337; 12, 3) ## extract message m' = 8 * (53 + 1468 * 12) mod 23 = 17 The formula for message extraction is derived by transposing the signature value s calculation formula. * s = m'^{-1} * (h + xr) mod q * s * m' = h + xr mod q * m' = s^{-1} * (h + xr) mod q Improvements A modification to the Brickell and DeLaurentis signature scheme provides a broadband channel without the necessity to share the authentication key Gustavus J. Simmons. A Secure Subliminal Channel (?). In CRYPTO ’85: Advances in Cryptology, pages 33–41, London, UK, 1986. Springer-Verlag.. The Newton channel is not a subliminal channel, but it can be viewed as an enhancement Ross J. Anderson, Serge Vaudenay, Bart Preneel, and Kaisa Nyberg. The Newton Channel. In Proceedings of the First International Workshop on Information Hiding, pages 151–156, London, UK, 1996. Springer-Verlag.. Countermeasures With the help of the Zero-knowledge proof and the Commitment scheme it is possible to prevent the usage of the subliminal channel Yvo Desmedt. Abuses in Cryptography and How to Fight Them. In CRYPTO ’88: Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, pages 375–389, London, UK, 1990. Springer-Verlag.. It should be mentioned that the countermeasure from has a 1-bit subliminal channel. The reason for that is the problem that a proof can succeed or purposely fail Yvo Desmedt. Simmons’ Protocol is Not Free of Subliminal Channels. In In Proc. of 9th IEEE Computer Security Foundations Workshop, pages 170–175, 1996.. Another countermeasures can detect, not prevent, the subliminal usage of the randomness Protecting Certiﬁcation Authorities and Jong Youl Choi. Tamper Evident Digital Signatures:. Technical report, In Proceedings of the Symposium on Dependable Autonomic and Secure Computing 2006, 2005.. References * Bruce Schneier. Applied Cryptography, Second Edition: Protocols, Algorithms, and Source Code in C, 2. Ed. Wiley Computer Publishing, John Wiley & Sons, Inc., 1995. External links * Seminar 'Covert Channels and Embedded Forensics' Category:Cryptography